package leetcode_401_500;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_401 {
    public static void main(String[] args) {
        System.out.println(readBinaryWatch(1));
        System.out.println(readBinaryWatch(9));
    }
    private static List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<>();
        dfs(ans, "", turnedOn);
        return ans;
    }
    private static void dfs(List<String> ans, String s, int remain){
        if (remain > 10 - s.length() || remain < 0)
            return;
        if (remain == 0 && s.length() == 10){
            int n1 = getNum(s.substring(0, 4));
            int n2 = getNum(s.substring(4, 10));
            if (n1 > 11 || n2 > 59)
                return;
            String s1 = n1 + "";
            String s2 = n2 + "";
            if (n2 / 10 == 0){
                s2 = "0" + s2;
            }
            ans.add(s1 + ":" + s2);
            return;
        }
        dfs(ans, s + "0", remain);
        dfs(ans, s + "1", remain - 1);
    }
    private static int getNum(String s){
        char[] cs = s.toCharArray();
        int n = cs.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (cs[i] == '1'){
                ans += Math.pow(2, n - i - 1);
            }
        }
        return ans;
    }
}
